package algorithm.linkedlist;

import algorithm.model.ListNode;

/**
 * leetcode : https://leetcode.com/problems/remove-linked-list-elements/description/
 * Diffculty: Easy
 *
 * 移除链表中指定元素
 * Input : 1->2->6->3->4->5->6, val = 6
 * Output : 1->2->3->4->5
 * @Author Antony
 * @Since 2018/7/8 22:14
 */
public class RemoveLinkedListElements {


    public static void main(String[] args) {
        ListNode initNode = ListNode.initDate(new int[]{1,2,6,3,4,5,6});
        initNode = removeElements_noObj(initNode, 6);
        System.out.println(initNode.nodeString());

        ListNode initNode_2 = ListNode.initDate(new int[]{1,1});
        initNode_2 = removeElements_noObj(initNode_2, 1);
        System.out.println(initNode_2.nodeString());

    }

    // (still 39.96% - 4ms)
    public static ListNode removeElements_twoPointer(ListNode head, int val) {
        if(head == null){
            return head;
        }
        while (head != null && head.val==val){
            head = head.next;
        }

        ListNode curr = head;
        ListNode pre = null;
        while(curr != null){
            if(curr.val==val){
                pre.next = curr.next;
            } else {
                pre = curr;
            }
            curr = curr.next;
        }

        return head;
    }

    /**
     * 尝试不创建新对象 (beats 40.05% - 4ms)
     * 先尝试清除head前面值相同的元素，直到找到一个head.val不为val的节点
     *
     */
    public static ListNode removeElements_noObj(ListNode head, int val) {
        if(head == null){
            return head;
        }
        while(head != null && head.val == val){
            head = head.next;
        }
        ListNode first = head;
        while(head != null && head.next != null){
            if(head.next.val == val){
                head.next = head.next.next;
            }else {
                head = head.next;
            }
        }

        return first;
    }

    /**
     * 思路，创建一个傀儡对象，Next指针指向head. (beats 40.05% - 4ms)
     *
     * 重点：【需要保持上一个节点的指针】
     * 然后逐个向后移动，遇到 node.val==val 的，移动两个指针，否则，移动一个指针
     */
    public static ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        while(dummy.next != null){
            if(dummy.next.val == val){
                dummy.next = dummy.next.next;
            }else {
                dummy = dummy.next;
            }
        }

        return first.next;
    }
}
